package leetcode.code0765;


public class Solution extends Solution765 {

	private int[] sitIn;// sit[x] = y; x人坐在y位置
	private int[] sitOn;// sit[x] = y; x人坐在y对情侣位置
	private int[] stack2couple;// 放置错误的情侣
	private int[] couple2stack;// 错误的情侣在栈里的位置
	private int pstack;

	@Override
	public int minSwapsCouples(int[] row) {
		int N2 = row.length;
		sitIn = new int[N2];
		sitOn = new int[N2];
		stack2couple = new int[N2 >> 1];
		pstack = -1;
		couple2stack = new int[N2 >> 1];
		for (int i = 1, couple = 0; i < N2; i = i + 2, couple++) {
			sitIn[row[i - 1]] = i - 1;// sitIn[人] = 座位号
			sitIn[row[i]] = i;
			sitOn[row[i - 1]] = couple;// sitOn[人] = 情侣号
			sitOn[row[i]] = couple;
			if (row[i - 1] != this.another(row[i])) {
				stack2couple[++pstack] = couple;// 截至[0,pstack]放着所有出错的情侣对
				couple2stack[couple] = pstack;// 出错的情侣在栈里的那个位置
			}
		}
		if (pstack == -1)// 没有错的位置
			return 0;
		return this.f(row);
	}

	private int f(int[] row) {
		if (pstack == -1) {
			return 0;
		}
		int couple1 = stack2couple[pstack--];// 随便找一对儿情侣
		int sit11 = couple1 << 1;// couple1这对儿情侣对应的椅子sit11
		int sit12 = couple1 << 1 | 1;// couple1这对儿情侣对应的椅子sit12
		int a11 = row[sit11];// sit11上坐着
		int x = row[sit12];// sit12上坐着
		int a12 = this.another(a11);// 找a11的情侣a12
		int couple2 = this.sitOn[a12];// a12当前的情侣编号couple2
		int sit21 = this.sitIn[a12];// a12的座位号sit21
		int sit22 = this.another(sit21);// sit21的另一个坐错的椅子sit22
		int y = row[sit22];// sit22上坐的人
		if (this.another(x) == y) {// 经过这一次交换a11和a12坐一起了，巧了，坐错的x和y也是一对儿
			// 从栈中移除`巧了`的这一对儿，将栈中最后一个同栈中移除的错误情侣交换
			stack2couple[couple2stack[couple2]] = stack2couple[pstack--];
			return this.f(row) + 1;
		}
//		row[sit12] = a12; 理论上a11和a12坐一起了，实际上没必要交换
		row[sit21] = x;// a11错配的情侣x，坐到了a12的位置sit21上
		sitIn[x] = sit21;// 更新 x的座位号
		sitOn[x] = couple2;// 更新x的情侣号
		return this.f(row) + 1;
	}

	private int another(int one) {// 情侣编号
		return (one & 1) == 1 ? one - 1 : one + 1;
	}

//	private int markWrongPlace(int wrong, int index) {
//		return wrong | (1 << index);
//	}
//
//	private int markRightPlace(int wrong, int index) {
//		return wrong ^ (1 << index);
//	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
